class Solution(object):
    def kthGrammar(self, n, k):
        """
        :type n: int
        :type k: int
        :rtype: int
        """
        def search(n, k):
            if n == 1:
                return 0
            r = search(n - 1, k // 2)
            m = k % 2
            if r == 0:
                if m == 0:
                    return 0
                else:
                    return 1
            else:
                if m == 0:
                    return 1
                else:
                    return 0
        return search(n, k - 1)

data = Solution()
n = 3
k = 4
print(data.kthGrammar(n, k))
